#include "SBB.h"
#include "../MEMREF.h"
#include "utils.h"
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <cassert>

using namespace std;

SBB::SBB(std::ifstream &infile) : end_(false), locked_(false) {
  if (!infile.is_open())
	throw std::invalid_argument("input file not open");
  std::unique_ptr<char[]> buf(new char[sizeof(MA)]);
  while (GetBinaryEntry(infile, buf)) {
	MA &ref = *(MA *)buf.get();
	if (IsBinaryBoundary(ref)) {
	  const char *data = (const char *)(buf.get() + sizeof(MA));
	  if (IsBinaryCSBoundary(ref)) {
		if (ref.getStart() == (uint64_t)MEMREF::ENTER_CS)
		  recv_.push_back(ThreadCode(data, data + strlen(data)));
		else
		  locked_ = true;
	  }
	  return;
	}
	ma_container_.push_back(ref);
  }
  if (ma_container_.empty())
	end_ = true;
}

void SBB::Coalesce(int stage) {
  if (empty()) return;
  if (stage == 1)
	sort(begin(), end(), StartCmp);
  auto prev = begin();
  prev->getWritesBefore() = prev->getMode() ? 0 : 1;
  for (auto it = begin() + 1; it != end(); ++it) {
	if (it->getStart() > prev->getEnd()) {
	  it->getWritesBefore() = prev->getWritesBefore() + it->getMode() ? 0 : 1;
	  *++prev = *it;
	} else {
	  assert(it->getStart() <= prev->getEnd());
	  if (it->getMode() == prev->getMode()) {
		// Extend prev, just assign it since both have same mode bit.
		prev->mode_end = it->mode_end;
	  } else if (it->getMode()) { // Write intersects with read.
		it->getStart() = prev->getEnd();
		if (!it->empty()) {
		  it->getWritesBefore() = prev->getWritesBefore();
		  *(++prev) = *it;
		}
	  } else { // Read intersects with Write.
		prev->setEnd(it->getStart());
		it->getWritesBefore() = prev->getWritesBefore() + 1;
		if (prev->empty())
		  *prev = *it;
		else
		  *(++prev) = *it;
	  }
	}
  }
  size_t oldSize = size();
  ma_container_.resize(prev - begin() + 1);

#ifdef DEBUG
  if (oldSize - size())
	cout << "coalsced in stage " << stage  << ": "  << oldSize - size() << endl;
#endif
  if (stage == 1)
	// second stage.
	Coalesce(2);
  else {
#if  DEBUG ==  2
	// Verify.
	if (!empty()) {
	  for (auto it = begin() + 1; it != end(); ++it) {
		assert(!it->overlapWith(*(it - 1)) ||\
			(it->getStart() == (it - 1)->getEnd() && it->getMode() != (it - 1)->getMode()));
	  }
	}
#endif
  }
}

std::ostream &operator<<(std::ostream &os, const SBB &sbb) {
  if (!sbb.empty()) {
	for (auto const &rec : sbb)
	  os <<  rec << '\n';
  }
  return os;
}

void compute(const string &threadname, UMAP &threadToSBB, uint32_t i) {
  vector<SBB> &sbbs = *threadToSBB[threadname];
  SBB &sbb = sbbs[i];
  typedef pair<uint32_t, uint32_t> PAIR;
  if (!sbb.clocks_pred_.empty()) return; // Already reached here through recursion.
  if (!i) {
	sbb.clocks_pred_[threadname] = PAIR(0, 0);
	return;
  }

  SBB &sbb1 = sbbs[i - 1];
  compute(threadname, threadToSBB, i - 1);
  assert(sbb.clocks_pred_.empty());
  // sbb inherits sbb1's predecessors.
  for (auto &p : sbb1.clocks_pred_)
	sbb.clocks_pred_[p.first] = sbb1.clocks_pred_[p.first];

  PAIR &cur = sbb.clocks_pred_[threadname]; // cur = (0, 0)
  cur.second = i - 1;
  if (!sbb1.IsRecv()) {// Post.
	cur.first++;
  } else {
	// Construct new predecessor set.
	// For now we just handle mutex.
	assert(sbb.recv_.size() <= 1);
	for (auto &recvFrom : sbb.recv_) {
	  if (sbb.clocks_pred_.find(recvFrom.first) == sbb.clocks_pred_.end()) // New predecessor.
		sbb.clocks_pred_[recvFrom.first] = PAIR(0, recvFrom.second);
	  else {
		PAIR &p = sbb.clocks_pred_[recvFrom.first];
		p.second = max(p.second, recvFrom.second);
	  }
	}

	for (auto &p1 : sbb.clocks_pred_) {
	  compute(p1.first, threadToSBB, p1.second.second);
	  const string &predThread = p1.first;
	  if (predThread == threadname) continue; // Already inherited.
	  uint32_t newClock = 0;
	  SBB &predecessor = threadToSBB[predThread]->operator[](p1.second.second);
	  for (auto &p2 : sbb.clocks_pred_) {
		uint32_t clk;
		if (p2.first == predThread) {
		  clk = predecessor.clocks_pred_[predThread].first + 1;
		} else {
		  compute(p2.first, threadToSBB, p2.second.second);
		  SBB &oth = threadToSBB[p2.first]->operator[](p2.second.second);
		  clk = oth.clocks_pred_[predThread].first;
		}
		if (clk > newClock) newClock = clk;
	  }
	  p1.second.first = newClock;
	}
  }
}

void ComputeVectorClocks(UMAP &SBBGraph) {
  for (auto &p : SBBGraph) {
	cout << "computing thread: " << p.first << '\n';
	compute(p.first, SBBGraph, SBBGraph[p.first]->size() - 1);
  }
}

namespace {
  inline uint32_t WritesBetween(MA const &l, MA const &r) {
	return r.getWritesBefore() - l.getWritesBefore() + (l.getMode() ? 0 : 1);
  }

  inline void ReportRace(MA const &lma, MA const &rma) {
	printf(COLOR_YELLOW "[%-10p %-5u %-5s] [%-10p %-5u %-5s]\n" COLOR_RESET,
		(void *)lma.getStart(), lma.getWidth(), lma.getMode() ? "READ" : "WRITE",
		(void *)rma.getStart(), rma.getWidth(), rma.getMode() ? "READ" : "WRITE");
  }
}

//Complexity: O(nlogn).
RACEPAIR DRCheck(SBB const &left, SBB const &right) {
  size_t nrw = 0;
  size_t nww = 0;
  for (auto &ma : left) {
	auto lb = lower_bound(begin(right), end(right), ma);
	if (!ma.overlapWith(*lb)) continue;
	auto hb = upper_bound(begin(right), end(right), ma);

	size_t nwrites = WritesBetween(*lb, *(hb - 1));
	if (ma.getMode() && !nwrites) continue;
	// Actual race.
	if (ma.getMode())  nrw++;
	else nww++;
#ifdef DEBUG
	if (hb - lb > 1)
	  cout << ma << "  " <<  *lb <<  "  " << *(hb - 1)  << "  " << *hb << endl;
	else
	  cout << ma << "  " << *lb << endl;
#endif
  }
  return RACEPAIR(nww, nrw);
}

//Complexity: O(n*n), too expensive, basically useless.
RACEPAIR NaiveDRCheck(SBB const &left, SBB const &right) {
  size_t nrw = 0;
  size_t nww = 0;
  //if (left.IsLocked() && right.IsLocked()) return 0;
  for (auto const &lma : left)
	for (auto const &rma : right)
	  if (lma.overlapWith(rma) && !(lma.getMode() && rma.getMode())) {
		if (lma.getMode()) nrw++;
		else nww++;
		//ReportRace(lma, rma);
	  }
  return RACEPAIR(nww, nrw);
}

